package leetcode.code0312;

/**
 * 动态规划 + 辅助数组 <br>
 *
 * No.3
 *
 * @author CaoYu
 * @date 2021年10月3日
 * @description
 */
public class Solution extends Solution312 {

	@Override
	public int maxCoins(int[] nums) {
		int n = nums.length;
		int[] pre = new int[n + 2];
		pre[0] = 1;
		pre[n + 1] = 1;
		int[][] dp = new int[n + 1][n + 1];
		for (int i = 0; i < n; i++) {
			pre[i + 1] = nums[i];
		}
		for (int i = 1; i <= n; i++) {
			dp[i][i] = pre[i] * pre[i - 1] * pre[i + 1];
		}
		for (int l = n; l >= 1; l--) {
			for (int r = l + 1; r <= n; r++) {
				int max = dp[l + 1][r] + pre[l] * pre[l - 1] * pre[r + 1];
				max = Math.max(max, dp[l][r - 1] + pre[r] * pre[l - 1] * pre[r + 1]);
				for (int i = l + 1; i < r; i++) {
					max = Math.max(max, dp[l][i - 1] + dp[i + 1][r] + pre[i] * pre[l - 1] * pre[r + 1]);
				}
				dp[l][r] = max;
			}
		}
		return dp[1][n];
	}

	public int f(int[] nums, int l, int r, Integer[][] dp) {
		if (dp[l][r] != null)
			return dp[l][r];
		if (l == r) {
			dp[l][r] = nums[l - 1] * nums[l] * nums[l + 1];
			return dp[l][r];
		}
		int max = f(nums, l + 1, r, dp) + nums[l] * nums[l - 1] * nums[r + 1];
		max = Math.max(max, f(nums, l, r - 1, dp) + nums[r] * nums[l - 1] * nums[r + 1]);
		for (int i = l + 1; i < r; i++) {
			max = Math.max(max, f(nums, l, i - 1, dp) + f(nums, i + 1, r, dp) + nums[i] * nums[l - 1] * nums[r + 1]);
		}
		dp[l][r] = max;
		return max;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
